/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.rop.code;

import com.android.dx.rop.type.StdTypeList;
import com.android.dx.rop.type.TypeList;
import com.android.dx.util.Hex;
import com.android.dx.util.IntList;
import com.android.dx.util.LabeledList;

/**
 * List of {@link BasicBlock} instances.
 */
public final class BasicBlockList extends LabeledList {

	/**
	 * {@code >= -1;} the count of registers required by this method or
	 * {@code -1} if not yet calculated
	 */
	private int regCount;

	/**
	 * Constructs an instance. All indices initially contain {@code null}, and
	 * the first-block label is initially {@code -1}.
	 * 
	 * @param size
	 *            the size of the list
	 */
	public BasicBlockList(int size) {
		super(size);

		regCount = -1;
	}

	/**
	 * Constructs a mutable copy for {@code getMutableCopy()}.
	 * 
	 * @param old
	 *            block to copy
	 */
	private BasicBlockList(BasicBlockList old) {
		super(old);
		regCount = old.regCount;
	}

	/**
	 * Gets the element at the given index. It is an error to call this with the
	 * index for an element which was never set; if you do that, this will throw
	 * {@code NullPointerException}.
	 * 
	 * @param n
	 *            {@code >= 0, < size();} which index
	 * @return {@code non-null;} element at that index
	 */
	public BasicBlock get(int n) {
		return (BasicBlock) get0(n);
	}

	/**
	 * Sets the basic block at the given index.
	 * 
	 * @param n
	 *            {@code >= 0, < size();} which index
	 * @param bb
	 *            {@code null-ok;} the element to set at {@code n}
	 */
	public void set(int n, BasicBlock bb) {
		super.set(n, bb);

		// Reset regCount, since it will need to be recalculated.
		regCount = -1;
	}

	/**
	 * Returns how many registers this method requires. This is simply the
	 * maximum of register-number-plus-category referred to by this instance's
	 * instructions (indirectly through {@link BasicBlock} instances).
	 * 
	 * @return {@code >= 0;} the register count
	 */
	public int getRegCount() {
		if (regCount == -1) {
			RegCountVisitor visitor = new RegCountVisitor();
			forEachInsn(visitor);
			regCount = visitor.getRegCount();
		}

		return regCount;
	}

	/**
	 * Gets the total instruction count for this instance. This is the sum of
	 * the instruction counts of each block.
	 * 
	 * @return {@code >= 0;} the total instruction count
	 */
	public int getInstructionCount() {
		int sz = size();
		int result = 0;

		for (int i = 0; i < sz; i++) {
			BasicBlock one = (BasicBlock) getOrNull0(i);
			if (one != null) {
				result += one.getInsns().size();
			}
		}

		return result;
	}

	/**
	 * Gets the total instruction count for this instance, ignoring mark-local
	 * instructions which are not actually emitted.
	 * 
	 * @return {@code >= 0;} the total instruction count
	 */
	public int getEffectiveInstructionCount() {
		int sz = size();
		int result = 0;

		for (int i = 0; i < sz; i++) {
			BasicBlock one = (BasicBlock) getOrNull0(i);
			if (one != null) {
				InsnList insns = one.getInsns();
				int insnsSz = insns.size();

				for (int j = 0; j < insnsSz; j++) {
					Insn insn = insns.get(j);

					if (insn.getOpcode().getOpcode() != RegOps.MARK_LOCAL) {
						result++;
					}
				}
			}
		}

		return result;
	}

	/**
	 * Gets the first block in the list with the given label, if any.
	 * 
	 * @param label
	 *            {@code >= 0;} the label to look for
	 * @return {@code non-null;} the so-labelled block
	 * @throws IllegalArgumentException
	 *             thrown if the label isn't found
	 */
	public BasicBlock labelToBlock(int label) {
		int idx = indexOfLabel(label);

		if (idx < 0) {
			throw new IllegalArgumentException("no such label: "
					+ Hex.u2(label));
		}

		return get(idx);
	}

	/**
	 * Visits each instruction of each block in the list, in order.
	 * 
	 * @param visitor
	 *            {@code non-null;} visitor to use
	 */
	public void forEachInsn(Insn.Visitor visitor) {
		int sz = size();

		for (int i = 0; i < sz; i++) {
			BasicBlock one = get(i);
			InsnList insns = one.getInsns();
			insns.forEach(visitor);
		}
	}

	/**
	 * Returns an instance that is identical to this one, except that the
	 * registers in each instruction are offset by the given amount. Mutability
	 * of the result is inherited from the original.
	 * 
	 * @param delta
	 *            the amount to offset register numbers by
	 * @return {@code non-null;} an appropriately-constructed instance
	 */
	public BasicBlockList withRegisterOffset(int delta) {
		int sz = size();
		BasicBlockList result = new BasicBlockList(sz);

		for (int i = 0; i < sz; i++) {
			BasicBlock one = (BasicBlock) get0(i);
			if (one != null) {
				result.set(i, one.withRegisterOffset(delta));
			}
		}

		if (isImmutable()) {
			result.setImmutable();
		}

		return result;
	}

	/**
	 * Returns a mutable copy of this list.
	 * 
	 * @return {@code non-null;} an appropriately-constructed instance
	 */
	public BasicBlockList getMutableCopy() {
		return new BasicBlockList(this);
	}

	/**
	 * Gets the preferred successor for the given block. If the block only has
	 * one successor, then that is the preferred successor. Otherwise, if the
	 * block has a primay successor, then that is the preferred successor. If
	 * the block has no successors, then this returns {@code null}.
	 * 
	 * @param block
	 *            {@code non-null;} the block in question
	 * @return {@code null-ok;} the preferred successor, if any
	 */
	public BasicBlock preferredSuccessorOf(BasicBlock block) {
		int primarySuccessor = block.getPrimarySuccessor();
		IntList successors = block.getSuccessors();
		int succSize = successors.size();

		switch (succSize) {
		case 0: {
			return null;
		}
		case 1: {
			return labelToBlock(successors.get(0));
		}
		}

		if (primarySuccessor != -1) {
			return labelToBlock(primarySuccessor);
		} else {
			return labelToBlock(successors.get(0));
		}
	}

	/**
	 * Compares the catches of two blocks for equality. This includes both the
	 * catch types and target labels.
	 * 
	 * @param block1
	 *            {@code non-null;} one block to compare
	 * @param block2
	 *            {@code non-null;} the other block to compare
	 * @return {@code true} if the two blocks' non-primary successors are
	 *         identical
	 */
	public boolean catchesEqual(BasicBlock block1, BasicBlock block2) {
		TypeList catches1 = block1.getExceptionHandlerTypes();
		TypeList catches2 = block2.getExceptionHandlerTypes();

		if (!StdTypeList.equalContents(catches1, catches2)) {
			return false;
		}

		IntList succ1 = block1.getSuccessors();
		IntList succ2 = block2.getSuccessors();
		int size = succ1.size(); // Both are guaranteed to be the same size.

		int primary1 = block1.getPrimarySuccessor();
		int primary2 = block2.getPrimarySuccessor();

		if (((primary1 == -1) || (primary2 == -1)) && (primary1 != primary2)) {
			/*
			 * For the current purpose, both blocks in question must either both
			 * have a primary or both not have a primary to be considered equal,
			 * and it turns out here that that's not the case.
			 */
			return false;
		}

		for (int i = 0; i < size; i++) {
			int label1 = succ1.get(i);
			int label2 = succ2.get(i);

			if (label1 == primary1) {
				/*
				 * It should be the case that block2's primary is at the same
				 * index. If not, we consider the blocks unequal for the current
				 * purpose.
				 */
				if (label2 != primary2) {
					return false;
				}
				continue;
			}

			if (label1 != label2) {
				return false;
			}
		}

		return true;
	}

	/**
	 * Instruction visitor class for counting registers used.
	 */
	private static class RegCountVisitor implements Insn.Visitor {

		/** {@code >= 0;} register count in-progress */
		private int regCount;

		/**
		 * Constructs an instance.
		 */
		public RegCountVisitor() {
			regCount = 0;
		}

		/**
		 * Gets the register count.
		 * 
		 * @return {@code >= 0;} the count
		 */
		public int getRegCount() {
			return regCount;
		}

		/** {@inheritDoc} */
		public void visitPlainInsn(PlainInsn insn) {
			visit(insn);
		}

		/** {@inheritDoc} */
		public void visitPlainCstInsn(PlainCstInsn insn) {
			visit(insn);
		}

		/** {@inheritDoc} */
		public void visitSwitchInsn(SwitchInsn insn) {
			visit(insn);
		}

		/** {@inheritDoc} */
		public void visitThrowingCstInsn(ThrowingCstInsn insn) {
			visit(insn);
		}

		/** {@inheritDoc} */
		public void visitThrowingInsn(ThrowingInsn insn) {
			visit(insn);
		}

		/** {@inheritDoc} */
		public void visitFillArrayDataInsn(FillArrayDataInsn insn) {
			visit(insn);
		}

		/**
		 * Helper for all the {@code visit*} methods.
		 * 
		 * @param insn
		 *            {@code non-null;} instruction being visited
		 */
		private void visit(Insn insn) {
			RegisterSpec result = insn.getResult();

			if (result != null) {
				processReg(result);
			}

			RegisterSpecList sources = insn.getSources();
			int sz = sources.size();

			for (int i = 0; i < sz; i++) {
				processReg(sources.get(i));
			}
		}

		/**
		 * Processes the given register spec.
		 * 
		 * @param spec
		 *            {@code non-null;} the register spec
		 */
		private void processReg(RegisterSpec spec) {
			int reg = spec.getNextReg();

			if (reg > regCount) {
				regCount = reg;
			}
		}
	}
}
